package hot_100;

import java.util.HashMap;

public class 路径总和III {
    public static void main(String[] args) {

    }


    HashMap<Long, Integer> map = new HashMap<>();
    int ans = 0;
    int target;

    public int pathSum(TreeNode root, int targetSum) {
        target = targetSum;
        map.put(0L, 1);
        Dfs(root, 0L);
        return ans;
    }

    public void Dfs(TreeNode root, Long sum) {
        if (root == null)
            return;
        ans += map.getOrDefault(sum + root.val - target, 0);
        map.merge(sum + root.val, 1, Integer::sum);
        Dfs(root.left, sum + root.val);
        Dfs(root.right, sum + root.val);
        map.merge(sum + root.val, -1, Integer::sum);
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
